package com.ryujung.binary_tree.leetCode_938;

/**
 * Definition for a binary tree node.
 **/
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

/**
 * 给定二叉搜索树的根结点 root，返回 L 和 R（含）之间的所有结点的值的和。 二叉搜索树保证具有唯一的值。
 * 
 * 示例 1： 输入：root = [10,5,15,3,7,null,18], L = 7, R = 15 输出：32
 * 
 * 示例 2： 输入：root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10 输出：23
 */
class Solution {
    /**
     * 遍历搜索树找到值在L和R之间的数, 求它们的和
     * 思路:  递归,深度优先.
     * 1.如果root值<小的值L,那么只需要遍历root的右子树,将符合条件的值累加
     * 2.如果root值>大的值R,那么只需要遍历root的左子树,将符合条件的值累加
     * 3.如果两种都不是就需要遍历左、右子树找到符合条件的值并加root.val的值
     * 4.递归深度优先遍历
     */
    public int rangeSumBST(TreeNode root, int L, int R) {
        int sum = 0;
        if (root == null){
            return 0;
        }

        if (root.val < L) {
            return rangeSumBST(root.right, L, R);
        }
        if (root.val > R) {
            return rangeSumBST(root.left, L, R);
        }
        //L<val<R的情况:
        sum += rangeSumBST(root.left, L, R)+rangeSumBST(root.right, L, R)+root.val;
        return sum;
    }
}